package TwoPointers;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class _524_LongestWordinDictionarythroughDeleting {
    //optimise method:use a temp word to save the local best answer instead of add to a list then sort it.
    public String findLongestWord(String s, List<String> d) {
        if(s.length()==0 || d.size()==0) return "";
        List<String> res = new ArrayList<>();
        int slength = s.length();
        for (String word : d) {
            int length = 0;
            int wlength = word.length();
            for (int i = 0; i < slength; i++) {
                if (s.charAt(i) == word.charAt(length)) {
                    length++;
                }
                if (length == wlength) {
                    res.add(word);
                    break;
                }
            }
        }
        Collections.sort(res,(w1,w2)->w1.length()==w2.length()?w1.compareTo(w2):w2.length()-w1.length());
        return res.size()==0?"":res.get(0);
    }
}
